#include <stdio.h>

int quickpass(int *a, int i, int j)
{
    int x = a[i];
    while (i < j) {
        while (i < j && a[j] >= x)
            j --;
        a[i] = a[j];

        while (i < j && a[i] <= x)
            i ++;
        a[j] = a[i];
    }
    a[i] = x;

    return i;
}

void quicksort(int *a, int i, int j)
{
    int k;

    if (i < j) {
        k = quickpass(a, i, j);
        quicksort(a, i, k-1);
        quicksort(a, k+1, j);
    }
}

int main(int argc, char *argv[])
{
    int i, n;

    int a[] = {9, 49, 65, 97, 76, 13, 27, 49};
    n = sizeof(a)/sizeof(int);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    quicksort(a, 0, n-1);

    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}
